package LC;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/combination-sum/description/
 * Given a set of candidate numbers (C) (without duplicates)
 * and a target number (T), find all unique combinations in C
 * where the candidate numbers sums to T.
 * The same repeated number may be chosen from C unlimited number of times.
 * Note:
 * All numbers (including target) will be positive integers.
 * The solution set must not contain duplicate combinations.
 * For example, given candidate set [2, 3, 6, 7] and target 7,
 * A solution set is:
 * [
 * [7],
 * [2, 2, 3]
 * ]
 */
public class LC_039_CombinationSum_DFS_BackTracking {
    public static void main(String[] args) {
        int[] candidates = {1, 2, 3, 4, 5};
        int target = 6;
        List<List<Integer>> res = Solution.combinationSum(candidates, target);
        System.out.println(res.toString());
    }

    static class Solution {
        static List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> item = new ArrayList<>();
            Arrays.sort(candidates);
            helper(candidates, target, 0, 0, item, res);
            return res;
        }

        private static void helper(int[] candidates, int target, int sum, int start, List<Integer> item, List<List<Integer>> result) {
            if (sum == target) {
                result.add(new ArrayList<>(item));
            } else if (sum < target) {
                for (int i = start; i < candidates.length; i++) {
                    item.add(candidates[i]);
                    helper(candidates, target, sum + candidates[i], i, item, result);
                    item.remove(item.size() - 1);
                }
            }
        }

    }
}
